This invention relates generally to systems and methods for verifying identity of people, by comparison and interpretation of skin patterns such as fingerprints; and more particularly to novel firmware and software stored in apparatus memories, as portions of apparatus, for interpreting such patterns and controlling utilization devices. With respect to certain of the appended claims, the invention further relates to systems that include such utilization devices.
A utilization device is, for example, a facility, apparatus, means for providing a financial service, or means for providing information. The phrase xe2x80x9cutilization devicexe2x80x9d thus encompasses, but is not limited to, businesses, homes, vehicles, automatic teller machines, time-and-attendance systems, database-searching services, and a great many other practical systems. An apparatus memory for such storage is, for example, a programmable read-only memory (xe2x80x9cPROMxe2x80x9d), or a computer-readable disc.
Classical methods for evaluation of fingerprints. toe-prints, palmprints and like skin patterns entail location, categorization and tabulation of minutiae. Efforts to adapt these classical techniques for automated print verification have received great attention and elaboration, but are fundamentally limited by their sensitivity to measurement noise at the location of the minutiae.
Automated analysis based on minutiae also is inherently very dependent on image enhancementxe2x80x94which often breaks down when initial data quality is marginal. For these reasons some workers have explored other methodologies.
Some seemingly promising efforts employ hologramsxe2x80x94either direct three-dimensional images of prints, or holographic Fourier transforms (which have the advantage of being position invariant). Some of these techniques, for best results, impose costly demands on special memory devices for storing the holograms. These holographic correlators are in essence modern refinements of much earlier two-dimensional direct-optical-overlay correlators such as that described by Green and Halasz in U.S. Pat. No. 3,928,842.
An intermediate ground is represented by a few relatively sophisticated patents that use digital computers to (1) automatically select one or more distinctive small regionsxe2x80x94not necessarily minutiaexe2x80x94in a master print or xe2x80x9ctemplatexe2x80x9d, and then (2) automatically look for one or more of these selected small regions in a print provided by a person who purports to be the maker of the template. These earlier patents particularly include U.S. Pat. No. 5,067,162 of Driscoll, U.S. Pat. No. 5,040,223 of Kamiya, U.S. Pat. No. 4,982,439 of Castelaz, U.S. Pat. No. 4,805,223 of Denyer, and U.S. Pat. No. 4,803,734 of Onishi.
All of these latter patents describe making final verification decisions based upon such comparisons of small regions. In this they are unavoidably flawed in their excessive dependence upon isolated, small amounts of dataxe2x80x94more specifically, very small fractions of the available information in a candidate user""s print.
Some of the patents in the above list do describe sound techniques for one or another part of their respective processes. Some workers, such as Driscoll and Kamiya, use correlation methods (but electronic-data correlation methods, not optical correlation methods) to choose the small reference sections in the enrollment processxe2x80x94i.e., in forming the templatexe2x80x94and also in comparison of those regions with features in a candidate user""s print. Denyer similarly uses an approximation to such correlation technique.
These patents do generally allow for the possibility that the authorized user""s template may be shifted, or in other words translated, in placement of the print image on the sensor. Some (particularly Driscoll and Denyer) allow for the possibility that the template may be rotated too.
Driscoll discusses finding a least-squares-fit between plural reference regions and a potentially corresponding plurality of test regions in the candidate print. He suggests that departures from an ideal rotated pattern of the reference regions is to be accounted for by distortion of the fingertip in the course of placement on a sensor, but by his least-squares approach also suggests that such distortion is inherently xe2x80x9crandomxe2x80x9d in the sense of lacking internal correlation.
Whereas distortions of flesh-and-skin structures are in fact random in the sense of being modeled or modelable statistically, proper efforts at such modeling must take into account that neighboring portions of the structure exert influences upon one another, resulting in physical correlations. In short, neighbors are softly constrained.
Driscoll""s approach, in using a least-squares fitxe2x80x94to accommodate departures from a rigid rotation that underlies the distortionxe2x80x94in essence disregards such correlations; at best, he only considers a small part of the operative statistics. Denyer, too, briefly mentions (though in a much more generalized and tangential way) the possibility of somehow accounting for distortion.
All of these patents, however, fail to take account of dilations (or, to put it more completely, dilations or contractions) which an authorized user""s fingertip may undergoxe2x80x94relative to the same user""s established template. Such dilations may arise from variations in the pressure with which the finger is applied to an optical or other sensor (capacitive, variable-resistance etc.).
Such dilations may be expected to have at least a component which is invariant across the entire image, in other words a dilation without change of fingerprint shapexe2x80x94an isomorphic dilation. Furthermore all the above-mentioned patents fail to make systematic, controlled allowance for dilations and other forms of distortion that are differentialxe2x80x94which is to say, nonisomorphic.
Correlation methods, matched-filter methods, and (loosely speaking) related overlay-style techniques of comparison all fail totally in any area where a reference print is mismatched to a candidate print by as little as a quarter of the spacing between ridges. I have found that dilations and other distortions can and commonly do produce spurious mismatches locallyxe2x80x94over sizable areasxe2x80x94exceeding twice the spacing between ridges, that is, many times the minimum disruption which destroys correlation and thereby recognition.
Therefore, failure to account properly for either dilation (isomorphic distortion) or distortion (differential distortion) results in unacceptably high rates of failure to verify or recognize an authorized userxe2x80x94i.e., high rates of the so-called xe2x80x9cfalse rejectionxe2x80x9d or xe2x80x9ctype 1 errorxe2x80x9d. Artificial measures aimed at reducing this failure rate lead inevitably to the converse: unacceptably high rates of failure to reject unauthorized users, impostorsxe2x80x94i.e., high rates of the so-called xe2x80x9cfalse acceptancexe2x80x9d or xe2x80x9ctype 2 errorxe2x80x9d.
Merely allowing for some distortion, in a statistically uncontrolled way, can never cure this fundamental failing. Skin and flesh distortion does not affect prints in an uncorrelated way, but rather in partially systematic ways that arise from the physical character of skin and flesh. I believe that failure to account properly for distortion is the single greatest contributor to poor performance of fingerprint verifying systems heretofore.
Furthermore variations in habits of placement of a fingertip on a sensor tend to be somewhat systematic. These systematic properties of the print-forming process have their own statistically characteristic patternsxe2x80x94their own statistics.
In the context of any given comparison method, these special statistics exert particular characteristic effects on the results. All the patents mentioned above appear to ignore these statistics, in the process discarding very important information that bears strongly on verification decisions.
In addition, the patents listed above fail to make use of modern principles of decision theory and signal processing that have been used to great advantage in other fields. Driscoll, for instance, while discussing the final stages of his analysis in terms reminiscent of the established Neyman-Pierson analysis, does not appear to properly apply the principles of that analysis. Such principles have been importantly applied in industrial, military, and scientific pattern-recognition problems, but workers in the practical fingerprint field do not appear to be aware of these principles or in any event are not evidently using them.
Similarly none of the patents noted makes use of decisional downweighting of data from areas that are less certain or noisier; rather, to the extent that any consideration at all is given to such matters, noisy data are simply discardedxe2x80x94a very undesirable way to treat expensive data. Bandpassing of test data is not seen in these references, although certain other forms of filtering are used by Driscoll and others. Normalizing is likewise absentxe2x80x94except for trivial forms implicit in binarization or trinarization, used in many print analyzers. None of the noted patents teaches expression of test and template data, or comparison of such data with one another, in terms of local sinusoids.
Thus the skin-pattern verification field has failed to make good use of all available data, take effective account of dilations or distortions, make suitable allowance for known statistics of placement variation, and apply modern decisional and signal-processing tools. As can now be seen, the prior art in this field remains subject to significant problems, and the efforts outlined abovexe2x80x94although praiseworthyxe2x80x94have left room for considerable improvement.
The present invention introduces such improvement, and performs fingerprint verifications with an outstandingly high accuracy not available heretofore. The invention has several facets or aspects which are usable independentlyxe2x80x94although for greatest enjoyment of their benefits I prefer to use them together, and although they do have several elements in common. The common parts will be described first.
In its preferred apparatus embodiments, the present invention is apparatus for verifying the identity of a person. It operates by comparing (1) test data representing a two-dimensional test image of that person""s skin-pattern print with (2) reference data derived from a two-dimensional reference skin-pattern print image obtained during a prior enrollment procedure. Each of the apparatus embodiments includes some means for holding instructions for automatic operation of the other elements of the apparatus; these instruction-holding means include or make use of a nonvolatile memory device, and may be termed the xe2x80x9cnonvolatile memory meansxe2x80x9d.
Now in preferred embodiments of a first of its independent aspects, the apparatus includes some means for extracting from the test data an estimate of noise variance in the test data. For purposes of breadth and generality in expression of the invention, these means will be called simply the xe2x80x9cextracting meansxe2x80x9d; they extract a noise-variance estimate as a function of position in the test image.
The apparatus of this first facet of the invention also includes some means for comparing portions of the test and reference data, for corresponding positions in the two images. Once again for generality and breadth these means will be called the xe2x80x9ccomparing meansxe2x80x9d.
In addition the apparatus includes some means for weighting the importance of comparison for each portion. These meansxe2x80x94again the xe2x80x9cweighting meansxe2x80x9dxe2x80x94weight the importance of comparison for each portion in accordance with the noise-variance estimate for the corresponding position.
Also included are some means, responsive to the weighting means, for making an identity-verification decisionxe2x80x94identified here as the xe2x80x9cdecision-making meansxe2x80x9d.
The foregoing may be a description or definition of the first facet or aspect of the present invention in its broadest or most general terms. Even in such general or broad form, however, as can now be seen the first aspect of the invention significantly contributes to resolving the previously outlined problems of the prior art. In particular, the use of down-weighting for noisier regions of a print is a major step toward enabling use of essentially all available data.
All of the apparatus forms of the invention are preferably practiced incorporating some sensor means for acquiring the test data, and some means, responsive to the decision-making means, for operating a switch. Thus the invention provides a practical real-world system, not an abstraction.
Now turning to a second of the independent facets or aspects of the invention: in preferred embodiments of this second facet, the invention apparatus includes some means for deriving from the test data corresponding multilevel test data that are bandpassed and normalized. For reasons suggested earlier these means may be denoted the xe2x80x9cderiving meansxe2x80x9d.
For the purposes of this document the term xe2x80x9cnormalizexe2x80x9d is to be understood as describing a true stretching (or compression) of the dynamic range of data to a standard rangexe2x80x94while maintaining multilevel character of the data. This normalization thus is understood to be beyond the trivial forms seen in prior-art binarization and trinarization, which force all data to be only binary or at most trinary.
This apparatus also has comparing means related to those described above for the first aspectxe2x80x94but here the comparing means are for comparing portions of the bandpassed and normalized multilevel test data with the reference data. In addition it has decision-making means, also related to those described earlierxe2x80x94but here the decision-making means are responsive to the comparing means.
The foregoing may constitute a definition or description of the second facet or aspect of the present invention in its broadest or most general terms. Even in such general or broad form, however, as can now be seen the second aspect of the invention resolves the previously outlined problems of the prior art.
In particular such an apparatus by taking advantage of signal-enhancing techniques of bandpassing and normalization the invention improves both actual signal-to-noise relations and effective signal-to-noise relations in the system, in terms of best use of the available data-handling capability.
These advantages have not heretofore been enjoyed by skin-pattern verification systems. In this way this second facet of the invention too leads toward greater precision and accuracy in verifying prints.
In a third of its independent facets, the invention apparatus includes means for expressing the test data in the form of local sinusoids, and means for expressing the reference data in the form of local sinusoids. The apparatus also includes comparing meansxe2x80x94but here the comparing means compare portions of the sinusoidally expressed test data with the sinusoidally expressed reference data.
Decision-making means are also included, responsive to the comparing means as just defined. By operating on the data in sinusoidal form the invention in preferred embodiments of this third aspect is able to exploit many advanced signal-processing techniques, particularly including the Fast Fourier Transform (FFT), multiplicative operations in the frequency domain in lieu of convolutions in the spatial domain, back-transformations to find spatial results etc.xe2x80x94each of which saves a great amount of computational time and effort without loss of accuracy.
While optical Fourier transforms have been applied in holographic fingerprint systems, as mentioned earlier, neither sinusoidal representations nor Fourier treatment of digital data has heretofore been used in this field.
Preferred apparatus embodiments of the invention in a fourth of its independent facets include some means for deriving from the reference data a map of ridge spacing and direction. These deriving means also store the map as one or more vector wavenumber fields.
Further included are some means for comparing portions of the test data with the reference data; these comparing means include means for using the vector wavenumber fields to refine the comparing operation. The apparatus also includes decision-making means responsive to these comparing means.
While some earlier systems do make one or another type of ridge map, typical earlier uses proceed to direct comparison of the maps. None stores the map in the form of a vector wavenumber field for later use in refining a discrete comparing operation.
This aspect of the invention enables several extremely effective uses of the ridge spacing and direction data in adjustments of the authorized-user template for fairer comparison with a candidate user""s fingerprint. Such advantages will be more clearly seen in later sections of this document.
Apparatus of preferred embodiments according to a fifth independent aspect or facet of the invention includes some means for estimating the assumed dilation of the test image relative to a reference imagexe2x80x94i.e., xe2x80x9cdilation-estimating meansxe2x80x9d. The dilation here mentioned is to be understood as having a global characterxe2x80x94in other words, affecting the entire print uniformly, without change of shape. The dilation-estimating means thus estimate isomorphic dilation.
The apparatus also includes means for comparing the test data with the reference data, taking into account the estimated dilation. The apparatus also includes decision-making means that respond to these comparing means.
This facet of the invention too advances the art meaning-fully as it enables two major operating improvements. The first of these is finding small regions of a candidate-user print that correspond to selected distinctive regions of the authorized-user templatexe2x80x94even in the presence of dilations that would otherwise destroy the correlation and so impair recognition.
The second major operating improvement attributable to this fifth independent aspect of the invention is particularly efficient operation of a more-general distortion-estimating aspect of the invention that will be described below. My global-dilation evaluating feature gives the later distortion estimator a running start, in that the distortion estimator need seek only the spatially differential part of the overall distortionxe2x80x94perturbations, in other words, of the global, isomorphic dilation.
Apparatus according to a sixth independent aspect of the invention includes some means for estimating an assumed distortion of the test image relative to a reference image. Here the distortion under discussion particularly includes nonisomorphic distortion.
As will be understood, however, the distortion here mentioned typically also includes an isomorphic componentxe2x80x94to the extent that previous detection of and accounting for isomorphic dilation was imperfect, or perhaps was not provided at all. The apparatus also includes means for comparing the test data with the reference data, taking into account the estimated distortion; and decision-making means responsive to these comparing means.
Although all the independent aspects and facets of my invention make extremely important contributions to excellent performance of my invention, the distortion-estimating means resolve the root cause of what I consider the greatest single defect in prior systems. As suggested earlier, it is this defect that especially impairs the ability of prior systems to reliably recognize an authorized userxe2x80x94i.e., to recognize a clear, clean template which has simply been slightly distorted.
In particular the estimation of distortion enables application of the estimated distortion to approximately equalize the test and reference data with respect to the assumed distortion. The comparing means can then compare the thus-approximately-equalized test and reference data.
This can be done particularly straightforwardly, by using the estimated distortion to generate a matched filter for use in forming a test statistic. In both the filter generation and the actual use of the test statistic thereby formed, the system can readily be made to take into account estimated noise variance in the test data, as a function of position in the test image.
The distortion adjustment underlies and enables all such refinements. The result is an overall level of excellence in recognition of templates, even in the presence of unusual distortionsxe2x80x94leading in turn to truly extraordinary low error rates of both the xe2x80x9cfalse rejectionxe2x80x9d and xe2x80x9cfalse acceptancexe2x80x9d types.
Details of operation of the distortion-estimating meansxe2x80x94including demodulation of the test data, smoothing, down-sampling and then a cautiously expanding gradient search for the assumed distortion field, to avoid loss of phase registrationxe2x80x94will all be presented below.
In a seventh of its independent facets or aspects, preferred apparatus embodiments of the invention include some means for comparing the test data with the reference data to form a test statistic as the ratio, or logarithm of the ratio, of the likelihoods of two contrary hypotheses:
likelihood of obtaining the test image, assuming that the candidate user is the same person who also formed the reference fingerprint image (template), and
likelihood of obtaining the test image, assuming that a different person formed the reference print image.
This apparatus also includes decision-making means responsive to the test statistic.
This aspect of the invention thus for the first time in the fingerprint field makes proper use of established principles of decision theory. Print verifications are thereby placed on a sound footing that actually leads to the most conclusive decision that can justifiably be made from the available informationxe2x80x94no more, no less.
Fingerprint-based verifications of identity have long suffered from an absence of such sound operation. Advantageously my comparison means are combined with means for comparing the test statistic with a threshold value, preselected to impose a desired level of certainty in verification.
Preferred apparatus embodiments of yet an eighth independent facet or aspect of my invention diverge somewhat from the first seven. The apparatus here is for receiving surface-relief data from a sensor that acquires surface-relief data from a relieved surface such as a fingerxe2x80x94and in response controlling access to facilities, equipment, a financial service, or a system for providing or receiving information.
The apparatus is for use in the presence of an assumed dilation of the relieved surface. The apparatus includes a system for processing the received data to determine identity of the relieved surface. In addition to the previously mentioned instruction-holding memory means, this system includes:
means for analyzing the data to estimate the assumed dilation,
means for comparing the test data with reference data, taking into account the estimated dilation, and
means, responsive to the comparing means, for making an identity-verification decision.
In addition, the overall apparatus includes some means for applying the determined identity to control access to such facilities, equipment, financial service, or source or reception of information. Thus this aspect of the invention, while specifically incorporating the dilation-estimating feature mentioned above in connection with the fifth independent aspect, particularly focuses on and includes, as part of the invention, components that actually control access to various types of utilization means.
A ninth independent facet of the invention involves a further divergence, in that it is a secured system subject to access control based upon surface-relief data from a relieved surface such as a finger. This system is for use in the presence of an assumed distortion of the relieved surface. The system includes utilization means, susceptible to misuse in the absence of a particular such relieved surface that is related to an authorized user. The utilization means being selected from the group consisting of:
a facility,
apparatus,
means for providing a financial service, and
means for providing or receiving information.
In addition the system includes sensor means for acquiring surface-relief data from such a relieved surface.
The system also includes some means for processing the data to determine identity of the relieved surface, and for applying the determined identity to control access to the utilization means. These processing and applying means include, in addition to the instruction-holding memory means:
means for analyzing the data to estimate the assumed distortion,
means for comparing the test data with reference data related to the particular relieved surface related to the authorized user, taking into account the estimated distortion, and
means, responsive to the comparing means, for making an identity-verification decision.
Thus this aspect of the invention includes the utilization means themselves, as well as the access-control intermediary that is included in the eighth aspect of the invention.
While thus focusing on and including the utilization means, the invention makes use of the distortion-estimating feature discussed earlier in connection with the sixth independent facet of the invention.
In a tenth of its independent aspects or facets, preferred embodiments of the invention take the form of a method, rather than apparatus. This method is for verifying the identity of a person. The method does so by comparing test data representing a two-dimensional test image of that person""s skin-pattern print with reference data derived from a two-dimensional reference skin-pattern print image obtained during a prior enrollment procedure.
The method includes the step of extracting from the test data an estimate of noise variance in the test data as a function of position in the test image. It also includes the step of comparing portions of the test and reference data, for corresponding positions in the two images.
Furthermore the method includes the steps of weighting the importance of comparison for each portion, in accordance with the noise-variance estimate for the corresponding position; andxe2x80x94responsive to the weighting meansxe2x80x94making an identity-verification decision. Another step is, in nonvolatile memory, holding instructions for automatic operation of the foregoing steps.
Thus the method partakes of the advantageousness of the noise-weighting apparatus embodiments of the first independent aspect of the invention, discussed earlier. Preferably this method is optimized by incorporation of other features or characteristics, particularly the steps of operating a sensor to acquire the test data andxe2x80x94responsive to the decision-making stepxe2x80x94operating a switch if identity is verified.
All of the foregoing operational principles and advantages of the present invention will be more fully appreciated upon consideration of the following detailed description, with reference to the appended drawings, of which: